package leetcode_500;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 *@author 周杨
 *PacificAtlanticWaterFlow_417  水流流向问题 需要找出能双向流动的区域
 *describe:深度优先遍历 并非单纯两个方向遍历 AC 62%
 *2018年7月24日 下午12:04:56
 */
public class PacificAtlanticWaterFlow_417 {
	
	public static void main(String[] args) {
		int[][] matrix=new int[][] {
			{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},
			{6,7,1,4,5},{5,1,1,2,4}
		};
		
		int[][] matrix1=new int[][] {
			{1,1},{1,1},{1,1},
		};
		PacificAtlanticWaterFlow_417 test=new PacificAtlanticWaterFlow_417();
		test.pacificAtlantic(matrix1);
	}
	
	 /**
	 * describe:记录双向流动可行的区域 但是遍历顺序出了问题 应该用深度优先遍历
	 * 2018年7月24日 下午12:03:01
	 */
	public List<int[]> pacificAtlantic(int[][] matrix) {
	        List<int[]>res=new ArrayList<int[]>();
	        if(matrix.length==0||matrix[0].length==0)
	        	return res;
	        int row=matrix.length,col=matrix[0].length;
	        boolean dp1[][]=new boolean[row][col];//保存能流到Atlantic的数据
	        boolean dp2[][]=new boolean[row][col];//保存能流到Pacfic的数据
	        for(int i=0;i<col;++i)
	        	dp1[0][i]=true;
	        for(int i=1;i<row;++i)
	        	dp1[i][0]=true;
	        int index=1;
	        while(index<row&&index<col) {
	        	if(index<row) {
	        		for(int i=index;i<col;++i) {
	        			dp1[index][i]=(dp1[index-1][i]&&(matrix[index][i]>=matrix[index-1][i]))||
	        					(dp1[index][i-1]&&matrix[index][i]>=matrix[index][i-1])?true:false;
	        		}
	        	}
	        	if(index<col) {
	        		for(int i=index+1;i<row;++i) {
	        			dp1[i][index]=dp1[i-1][index]&&matrix[i][index]>=matrix[i-1][index]||
	        					dp1[i][index-1]&&matrix[i][index]>=matrix[i][index-1]?true:false;
	        		}
	        	}
	        	++index;
	        }
	        for(int i=row-1;i>=0;--i) {
	        	dp2[i][col-1]=true;
	        	if(dp1[i][col-1]) {
	        		res.add(new int[] {i,col-1});
	        	}
	        }
	        for(int i=col-2;i>=0;--i) {
	        	dp2[row-1][i]=true;
	        	if(dp1[row-1][i]) {
	        		res.add(new int[] {row-1,i});
	        	}
	        }
	        index=1;
	        while(row>index&&col>index) {
	        	if(row>index) {
	        		for(int i=row-1-index;i>=0;--i) {
	        				if(dp2[i+1][col-1-index]&&matrix[i][col-1-index]>=matrix[i+1][col-1-index]||
	        						dp2[i][col-index]&&matrix[i][col-1-index]>=matrix[i][col-index]) {
	    	        			if(dp1[i][col-1-index]) {
	    	        				res.add(new int[] {i,col-1-index});
	    	        			}
	        					dp2[i][col-1-index]=true;
	        			}
	        		}
	        	}
	        	if(col>index) {
	        		for(int i=col-2-index;i>=0;--i) {
	        				if(dp2[row-index][i]&&matrix[row-1-index][i]>=matrix[row-index][i]||
	        						dp2[row-index-1][i+1]&&matrix[row-1-index][i]>=matrix[row-index-1][i+1]) {
	    	        			if(dp1[row-1-index][i]) {
	    	        				res.add(new int[] {row-1-index,i});
	    	        			}
	        					dp2[row-1-index][i]=true;
	        				}
	        			}
	        	}
	        	++index;
	        }
	        
	        return res;
	 }
	
	 public List<int[]> pacificAtlantic1(int[][] matrix) {
	        List<int[]> res = new LinkedList<>();
	        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
	            return res;
	        }
	        int n = matrix.length, m = matrix[0].length;
	        boolean[][]pacific = new boolean[n][m];
	        boolean[][]atlantic = new boolean[n][m];
	        for(int i=0; i<n; i++){
	            dfs(matrix, pacific, Integer.MIN_VALUE, i, 0);
	            dfs(matrix, atlantic, Integer.MIN_VALUE, i, m-1);
	        }
	        for(int i=0; i<m; i++){
	            dfs(matrix, pacific, Integer.MIN_VALUE, 0, i);
	            dfs(matrix, atlantic, Integer.MIN_VALUE, n-1, i);
	        }
	        for (int i = 0; i < n; i++) 
	            for (int j = 0; j < m; j++) 
	                if (pacific[i][j] && atlantic[i][j]) 
	                    res.add(new int[] {i, j});
	        return res;
	    }
	    
	    int[][]dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
	    
	    public void dfs(int[][]matrix, boolean[][]visited, int height, int x, int y){
	        int n = matrix.length, m = matrix[0].length;
	        if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < height)
	            return;
	        visited[x][y] = true;
	        for(int[]d:dir){
	            dfs(matrix, visited, matrix[x][y], x+d[0], y+d[1]);
	        }
	    }
}
